package 分割回文串;



import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 分割回文串
 * @date 2022/11/14 9:52
 */
public class Demo131 {
    List<List<String>> res=new ArrayList<>();
    List<String> path=new ArrayList<>();
    public List<List<String>> partition(String s) {

          backTrack(s,0);
          return res;
    }

    private void backTrack(String s, int startIndex) {
        //画图可以很好证明，startIndex 就是分割线
        //startIndex ==s.length 则证明已经分割完成了可以返回了
        if(startIndex==s.length()){
            res.add(new ArrayList<>(path));
        }
        //回溯三部曲
        for (int i = startIndex; i < s.length(); i++) {
             if(isHuiWen(s,startIndex,i)){
                 //如果是回文，则将字串加到path
                 path.add(s.substring(startIndex,i+1));
             }else {
                 //不是回文则进行
                 continue;
             }
             //进行回溯
             backTrack(s,i+1);
             path.remove(path.size()-1);
        }
    }

    private boolean isHuiWen(String s, int startIndex, int i) {
        while (startIndex<i){
            if(s.charAt(startIndex++)!=s.charAt(i--)){
                return false;
            }
        }
        return true;
    }

}
